#include "removeDuplicateLetters.h"
std::string removeDuplicateLetters(std::string s) {
  int *count_chars = new int[26];
  std::fill(count_chars, count_chars + 26, 0);
  // 找到字符最后一次出现的位置
  for (int i = 0; i < s.size(); i++) count_chars[s.at(i) - 'a'] = i;
  bool *in_stack = new bool[26];
  std::fill(in_stack, in_stack + 26, false);
  std::string res = "";  // 字符串模拟栈
  for (int i = 0; i < s.size(); i++) {
    char current_char = s.at(i);
    if (in_stack[current_char - 'a']) {
      continue;
    }
    if (res.empty()) {
      res.push_back(current_char);
      in_stack[current_char - 'a'] = true;
      continue;
    }
    while (!res.empty() && current_char < *res.rbegin() &&
           count_chars[*res.rbegin() - 'a'] > i) {
      in_stack[*res.rbegin() - 'a'] = false;
      res.pop_back();
    }
    if (res.empty() || (!res.empty() && !in_stack[current_char - 'a'])) {
      res.push_back(current_char);
      in_stack[current_char - 'a'] = true;
    }
  }
  delete[] count_chars;
  delete[] in_stack;
  return res;
}
